Java并发编程笔记4-ThreadLocalRandom 类原理剖析

概览（本文逻辑）

首先本文先介绍了Random的类的使用，以及Random类在多线程中遇到的问题：多线程中如何不生成大量重复的数据。
然后我们知道了Random类的解决方式，也就是使用了原子变量作为种子的类型，这样就解决了问题，但是这样解决又遇到了一个新的问题，就是多线程种子的恶意竞争导致效率低下。
为了解决这个问题，借用了ThreadLocal的思想产生了ThreadLocalRandom ，它让每个线程内部持有一个本地的种子变量，这样每个线程都会根据自己内部的种子进行更新，从而避免了竞争。而且这个种子变量只有在使用随机数的时候才会被初始化，这样延迟初始化的思路，也值得参考。
详细的介绍了ThreadLocalRandom 内部的代码。

JDK 并发包中 ThreadLocalRandom 类原理剖析

ThreadLocalRandom 类是 JDK7 在 JUC 包下新增的随机数生成器，它解决了 Random 类在多线程下的不足。本节就来讲解下 JUC 下为何新增该类，以及该类的实现原理。

Random类的局限性

java.util.Random 类是一个日常使用较多的工具类，用法也很简单，如下：

public class RandomTest {
    public static void main(String[] args) {

        //(1)创建一个默认种子的随机数生成器
        Random random = new Random();
        //(2)输出10个在0-5（包含0，不包含5）之间的随机数
        for (int i = 0; i < 10; ++i) {
            System.out.println(random.nextInt(5));
        }
    }
}

这里有一个概念是随机种子，这个概念再numpy中也经常被提及，随机种子一定，每次生成的随机数是一样的。
我们看如下的代码，看看Java中随机种子部分：

public int nextInt(int bound) {
    //(3)参数检查
    if (bound <= 0)
        throw new IllegalArgumentException(BadBound);
    //(4)根据老的种子生成新的种子
    int r = next(31);
    //(5)根据新的种子计算随机数
    ...
    return r;
}

根据这部分源码，我们可以看出在第一个例子中，代码（2）循环中nextInt它的步骤应当是：

首先根据老种子生成新种子
根据新种子生成随机数

这种算法在单线程部分是没什么问题的，但是在多线程部分，由于可能拿同一个老的种子去生成数据，而（5）的算法是不变的，这样就会导致多线程生成的随机数有大量的重复，这就是问题了。

这个问题拿到了，实际上是有一定思路的，我们只需要保证（4）的代码的原子性，也就是说，下一个线程再来取种子的时候，取的是上一个线程刚生成的种子，这样就能解决问题了。

看next函数的具体代码

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        //(6)
        oldseed = seed.get();
        //(7)
        nextseed = (oldseed * multiplier + addend) & mask;
        //(8)
    } while (!seed.compareAndSet(oldseed, nextseed));
    //(9)
    return (int)(nextseed >>> (48 - bits));
}

代码（6）获取当前原子变量种子的值；
代码（7）根据当前种子值计算新的种子；
代码（8）使用 CAS 操作，使用新的种子去更新老的种子，多线程下可能多个线程都同时执行到了代码（6），那么可能多个线程都拿到的当前种子的值是同一个，然后执行步骤（7）计算的新种子也都是一样的，但是步骤（8）的 CAS 操作会保证只有一个线程可以更新老的种子为新的，失败的线程会通过循环重新获取更新后的种子作为当前种子去计算老的种子，可见这里解决了上面提到的问题，也就保证了随机数的随机性。
代码（9）则使用固定算法根据新的种子计算随机数。

这就是Random内部对多线程的优化，每个 Random 实例里面有一个原子性的种子变量用来记录当前的种子的值，当要生成新的随机数时候要根据当前种子计算新的种子并更新回原子变量。多线程下使用单个 Random 实例生成随机数时候，多个线程同时计算新的种子时候会竞争同一个原子变量的更新操作，由于原子变量的更新是 CAS 操作，同时只有一个线程会成功，所以会造成大量线程进行自旋重试，这是会降低并发性能的，所以 ThreadLocalRandom 应运而生。

ThreadLocalRandom 类原理

为了解决多线程高并发下 Random 的缺陷，JUC 包下新增了 ThreadLocalRandom 类，下面首先看下它如何使用：

public class RandomTest {

    public static void main(String[] args) {
        //(10)获取一个随机数生成器
        ThreadLocalRandom random =  ThreadLocalRandom.current();

        //(11)输出10个在0-5（包含0，不包含5）之间的随机数
        for (int i = 0; i < 10; ++i) {
            System.out.println(random.nextInt(5));
        }
    }
}

看起来用法还是差不多的，既然它叫ThreadLocalRandom ，理所应当的，它借用了ThreadLocal中的一些思路，也就是每个线程中都拷贝一份变量，刚刚我们也说了，Random的缺陷是在于会使用AtomicLong 原子性种子变量，这会导致原子变量更新的恶意竞争，如下图：
Alt text

那么如果每个线程维护自己的一个种子变量，每个线程生成随机数时候根据自己老的种子计算新的种子，并使用新种子更新老的种子，然后根据新种子计算随机数，就不会存在竞争问题，这会大大提高并发性能，如下图 ThreadLocalRandom 原理：

Alt text

我们来看一下它的源码部分：
首先看一下的的类图结构：
Alt text

可知 ThreadLocalRandom 继承了 Random 并重写了 nextInt 方法，ThreadLocalRandom 中并没有使用继承自 Random 的原子性种子变量。

ThreadLocalRandom 中并没有具体存放种子，具体的种子是存放到具体的调用线程的 threadLocalRandomSeed 变量里面的，ThreadLocalRandom 类似于 ThreadLocal类就是个工具类。当线程调用 ThreadLocalRandom 的 current 方法时候 ThreadLocalRandom 负责初始化调用线程的 threadLocalRandomSeed 变量，也就是初始化种子。

当调用 ThreadLocalRandom 的 nextInt 方法时候，实际上是获取当前线程的 threadLocalRandomSeed 变量作为当前种子来计算新的种子，然后更新新的种子到当前线程的 threadLocalRandomSeed 变量，然后在根据新种子和具体算法计算随机数。

这里需要注意的是 threadLocalRandomSeed 变量就是 Thread 类里面的一个普通 long 变量，并不是原子性变量，其实道理很简单，因为这个变量是线程级别的，根本不需要使用原子性变量，如果还是不理解可以思考下 ThreadLocal 的原理。

其中变量 seeder 和 probeGenerator 是两个原子性变量，在初始化调用线程的种子和探针变量时候用到，每个线程只会使用一次。

另外变量 instance 是个 ThreadLocalRandom 的一个实例，该变量是 static 的，当多线程通过 ThreadLocalRandom 的 current 方法获取 ThreadLocalRandom 的实例时候其实获取的是同一个，但是由于具体的种子是存放到线程里面的，所以 ThreadLocalRandom 的实例里面只是与线程无关的通用算法，所以是线程安全的。

下面看看 ThreadLocalRandom 的主要代码实现逻辑。

private static final sun.misc.Unsafe UNSAFE;
private static final long SEED;
private static final long PROBE;
private static final long SECONDARY;
static {
    try {
        //获取unsafe实例
        UNSAFE = sun.misc.Unsafe.getUnsafe();
        Class<?> tk = Thread.class;
        //获取Thread类里面threadLocalRandomSeed变量在Thread实例里面偏移量
        SEED = UNSAFE.objectFieldOffset
            (tk.getDeclaredField("threadLocalRandomSeed"));
        //获取Thread类里面threadLocalRandomProbe变量在Thread实例里面偏移量
        PROBE = UNSAFE.objectFieldOffset
            (tk.getDeclaredField("threadLocalRandomProbe"));
        //获取Thread类里面threadLocalRandomProbe变量在Thread实例里面偏移量，这个值在后面讲解的LongAdder里面会用到
        SECONDARY = UNSAFE.objectFieldOffset
            (tk.getDeclaredField("threadLocalRandomSecondarySeed"));
    } catch (Exception e) {
        throw new Error(e);
    }
}

ThreadLocalRandom current() 方法：该方法获取 ThreadLocalRandom 实例，并初始化调用线程中 threadLocalRandomSeed 和 threadLocalRandomProbe 变量。

static final ThreadLocalRandom instance = new ThreadLocalRandom();
public static ThreadLocalRandom current() {
    //(12)
    if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)
        //(13)
        localInit();
    //(14)
    return instance;
}

static final void localInit() {
    int p = probeGenerator.addAndGet(PROBE_INCREMENT);
    int probe = (p == 0) ? 1 : p; // skip 0
    long seed = mix64(seeder.getAndAdd(SEEDER_INCREMENT));
    Thread t = Thread.currentThread();
    UNSAFE.putLong(t, SEED, seed);
    UNSAFE.putInt(t, PROBE, probe);
}

如上代码（12）如果当前线程中 threadLocalRandomProbe 变量值为0（默认情况下线程的这个变量为0），说明当前线程第一次调用 ThreadLocalRandom 的 current 方法，那么就需要调用 localInit 方法计算当前线程的初始化种子变量。这里设计为了延迟初始化，不需要使用随机数功能时候 Thread 类中的种子变量就不需要被初始化，这是一种优化。

代码（13）首先计算根据 probeGenerator 计算当前线程中 threadLocalRandomProbe 的初始化值，然后根据 seeder 计算当前线程的初始化种子，然后把这两个变量设置到当前线程。

代码（14）返回 ThreadLocalRandom 的实例，需要注意的是这个方法是静态方法，多个线程返回的是同一个 ThreadLocalRandom 实例。

int nextInt(int bound) 方法：计算当前线程的下一个随机数。

public int nextInt(int bound) {
    //(15)参数校验
    if (bound <= 0)
        throw new IllegalArgumentException(BadBound);
    //(16) 根据当前线程中种子计算新种子
    int r = mix32(nextSeed());
    //(17)根据新种子和bound计算随机数
    int m = bound - 1;
    if ((bound & m) == 0) // power of two
        r &= m;
    else { // reject over-represented candidates
        for (int u = r >>> 1;
             u + m - (r = u % bound) < 0;
             u = mix32(nextSeed()) >>> 1)
            ;
    }
    return r;
}

如上代码逻辑步骤与 Random 相似，我们重点看下 nextSeed() 方法：

final long nextSeed() {
    Thread t; long r; // 
    UNSAFE.putLong(t = Thread.currentThread(), SEED,
                   r = UNSAFE.getLong(t, SEED) + GAMMA);
    return r;
}